home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 5 / Apprentice-Release5.iso / Source Code / Libraries / Berkeley DB 1.8.5a / hash / hash.h < prev    next >
Text File  |  1995-10-08  |  10KB  |  302 lines
  1. /*-
  2.  * Copyright (c) 1990, 1993, 1994
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Margo Seltzer.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  *
  36.  *    @(#)hash.h    8.3 (Berkeley) 5/31/94
  37.  */
  38.  
  39. /* Operations */
  40. typedef enum {
  41.     HASH_GET, HASH_PUT, HASH_PUTNEW, HASH_DELETE, HASH_FIRST, HASH_NEXT
  42. } ACTION;
  43.  
  44. /* Buffer Management structures */
  45. typedef struct _bufhead BUFHEAD;
  46.  
  47. #if PRAGMA_ALIGN_SUPPORTED
  48. #pragma options align=mac68k
  49. #endif
  50.  
  51. struct _bufhead {
  52.     BUFHEAD        *prev;        /* LRU links */
  53.     BUFHEAD        *next;        /* LRU links */
  54.     BUFHEAD        *ovfl;        /* Overflow page buffer header */
  55.     u_int32_t     addr;        /* Address of this page */
  56.     char        *page;        /* Actual page data */
  57.     char         flags;
  58. #define    BUF_MOD        0x0001
  59. #define BUF_DISK    0x0002
  60. #define    BUF_BUCKET    0x0004
  61. #define    BUF_PIN        0x0008
  62. };
  63.  
  64. #define IS_BUCKET(X)    ((X) & BUF_BUCKET)
  65.  
  66. typedef BUFHEAD **SEGMENT;
  67.  
  68. /* Hash Table Information */
  69. typedef struct hashhdr {        /* Disk resident portion */
  70.     int        magic;        /* Magic NO for hash tables */
  71.     int        version;    /* Version ID */
  72.     u_int32_t    lorder;        /* Byte Order */
  73.     int        bsize;        /* Bucket/Page Size */
  74.     int        bshift;        /* Bucket shift */
  75.     int        dsize;        /* Directory Size */
  76.     int        ssize;        /* Segment Size */
  77.     int        sshift;        /* Segment shift */
  78.     int        ovfl_point;    /* Where overflow pages are being 
  79.                      * allocated */
  80.     int        last_freed;    /* Last overflow page freed */
  81.     int        max_bucket;    /* ID of Maximum bucket in use */
  82.     int        high_mask;    /* Mask to modulo into entire table */
  83.     int        low_mask;    /* Mask to modulo into lower half of 
  84.                      * table */
  85.     int        ffactor;    /* Fill factor */
  86.     int        nkeys;        /* Number of keys in hash table */
  87.     int        hdrpages;    /* Size of table header */
  88.     int        h_charkey;    /* value of hash(CHARKEY) */
  89. #define NCACHED    32            /* number of bit maps and spare 
  90.                      * points */
  91.     int        spares[NCACHED];/* spare pages for overflow */
  92.     u_int16_t    bitmaps[NCACHED];    /* address of overflow page 
  93.                          * bitmaps */
  94. } HASHHDR;
  95.  
  96. typedef struct htab     {        /* Memory resident data structure */
  97.     HASHHDR     hdr;        /* Header */
  98.     int        nsegs;        /* Number of allocated segments */
  99.     int        exsegs;        /* Number of extra allocated 
  100.                      * segments */
  101.     u_int32_t            /* Hash function */
  102.         (*hash)__P((const void *, size_t));
  103.     int        flags;        /* Flag values */
  104.     int        fp;        /* File pointer */
  105.     char        *tmp_buf;    /* Temporary Buffer for BIG data */
  106.     char        *tmp_key;    /* Temporary Buffer for BIG keys */
  107.     BUFHEAD     *cpage;        /* Current page */
  108.     int        cbucket;    /* Current bucket */
  109.     int        cndx;        /* Index of next item on cpage */
  110.     int        errno;        /* Error Number -- for DBM 
  111.                      * compatability */
  112.     int        new_file;    /* Indicates if fd is backing store 
  113.                      * or no */
  114.     int        save_file;    /* Indicates whether we need to flush 
  115.                      * file at
  116.                      * exit */
  117.     u_int32_t    *mapp[NCACHED];    /* Pointers to page maps */
  118.     int        nmaps;        /* Initial number of bitmaps */
  119.     int        nbufs;        /* Number of buffers left to 
  120.                      * allocate */
  121.     BUFHEAD     bufhead;    /* Header of buffer lru list */
  122.     SEGMENT     *dir;        /* Hash Bucket directory */
  123. } HTAB;
  124.  
  125. #if PRAGMA_ALIGN_SUPPORTED
  126. #pragma options align=reset
  127. #endif
  128.  
  129. /*
  130.  * Constants
  131.  */
  132. #define    MAX_BSIZE        65536        /* 2^16 */
  133. #define MIN_BUFFERS        6
  134. #define MINHDRSIZE        512
  135. #define DEF_BUFSIZE        65536        /* 64 K */
  136. #define DEF_BUCKET_SIZE        4096
  137. #define DEF_BUCKET_SHIFT    12        /* log2(BUCKET) */
  138. #define DEF_SEGSIZE        256
  139. #define DEF_SEGSIZE_SHIFT    8        /* log2(SEGSIZE)     */
  140. #define DEF_DIRSIZE        256
  141. #define DEF_FFACTOR        65536
  142. #define MIN_FFACTOR        4
  143. #define SPLTMAX            8
  144. #define CHARKEY            "%$sniglet^&"
  145. #define NUMKEY            1038583
  146. #define BYTE_SHIFT        3
  147. #define INT_TO_BYTE        2
  148. #define INT_BYTE_SHIFT        5
  149. #define ALL_SET            ((u_int32_t)0xFFFFFFFF)
  150. #define ALL_CLEAR        0
  151.  
  152. #define PTROF(X)    ((BUFHEAD *)((ptrdiff_t)(X)&~0x3))
  153. #define ISMOD(X)    ((u_int32_t)(ptrdiff_t)(X)&0x1)
  154. #define DOMOD(X)    ((X) = (char *)((ptrdiff_t)(X)|0x1))
  155. #define ISDISK(X)    ((u_int32_t)(ptrdiff_t)(X)&0x2)
  156. #define DODISK(X)    ((X) = (char *)((ptrdiff_t)(X)|0x2))
  157.  
  158. #define BITS_PER_MAP    32
  159.  
  160. /* Given the address of the beginning of a big map, clear/set the nth bit */
  161. #define CLRBIT(A, N)    ((A)[(N)/BITS_PER_MAP] &= ~(1<<((N)%BITS_PER_MAP)))
  162. #define SETBIT(A, N)    ((A)[(N)/BITS_PER_MAP] |= (1<<((N)%BITS_PER_MAP)))
  163. #define ISSET(A, N)    ((A)[(N)/BITS_PER_MAP] & (1<<((N)%BITS_PER_MAP)))
  164.  
  165. /* Overflow management */
  166. /*
  167.  * Overflow page numbers are allocated per split point.  At each doubling of
  168.  * the table, we can allocate extra pages.  So, an overflow page number has
  169.  * the top 5 bits indicate which split point and the lower 11 bits indicate
  170.  * which page at that split point is indicated (pages within split points are
  171.  * numberered starting with 1).
  172.  */
  173.  
  174. #define SPLITSHIFT    11
  175. #define SPLITMASK    0x7FF
  176. #define SPLITNUM(N)    (((u_int32_t)(N)) >> SPLITSHIFT)
  177. #define OPAGENUM(N)    ((N) & SPLITMASK)
  178. #define    OADDR_OF(S,O)    ((u_int32_t)((u_int32_t)(S) << SPLITSHIFT) + (O))
  179.  
  180. #define BUCKET_TO_PAGE(B) \
  181.     (B) + hashp->HDRPAGES + ((B) ? hashp->SPARES[__log2((B)+1)-1] : 0)
  182. #define OADDR_TO_PAGE(B)     \
  183.     BUCKET_TO_PAGE ( (1 << SPLITNUM((B))) -1 ) + OPAGENUM((B));
  184.  
  185. /*
  186.  * page.h contains a detailed description of the page format.
  187.  *
  188.  * Normally, keys and data are accessed from offset tables in the top of
  189.  * each page which point to the beginning of the key and data.  There are
  190.  * four flag values which may be stored in these offset tables which indicate
  191.  * the following:
  192.  *
  193.  *
  194.  * OVFLPAGE    Rather than a key data pair, this pair contains
  195.  *        the address of an overflow page.  The format of
  196.  *        the pair is:
  197.  *            OVERFLOW_PAGE_NUMBER OVFLPAGE
  198.  *
  199.  * PARTIAL_KEY    This must be the first key/data pair on a page
  200.  *        and implies that page contains only a partial key.
  201.  *        That is, the key is too big to fit on a single page
  202.  *        so it starts on this page and continues on the next.
  203.  *        The format of the page is:
  204.  *            KEY_OFF PARTIAL_KEY OVFL_PAGENO OVFLPAGE
  205.  *        
  206.  *            KEY_OFF -- offset of the beginning of the key
  207.  *            PARTIAL_KEY -- 1
  208.  *            OVFL_PAGENO - page number of the next overflow page
  209.  *            OVFLPAGE -- 0
  210.  *
  211.  * FULL_KEY    This must be the first key/data pair on the page.  It
  212.  *        is used in two cases.
  213.  *
  214.  *        Case 1:
  215.  *            There is a complete key on the page but no data
  216.  *            (because it wouldn't fit).  The next page contains
  217.  *            the data.
  218.  *
  219.  *            Page format it:
  220.  *            KEY_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  221.  *
  222.  *            KEY_OFF -- offset of the beginning of the key
  223.  *            FULL_KEY -- 2
  224.  *            OVFL_PAGENO - page number of the next overflow page
  225.  *            OVFLPAGE -- 0
  226.  *
  227.  *        Case 2:
  228.  *            This page contains no key, but part of a large
  229.  *            data field, which is continued on the next page.
  230.  *
  231.  *            Page format it:
  232.  *            DATA_OFF FULL_KEY OVFL_PAGENO OVFL_PAGE
  233.  *
  234.  *            KEY_OFF -- offset of the beginning of the data on
  235.  *                this page
  236.  *            FULL_KEY -- 2
  237.  *            OVFL_PAGENO - page number of the next overflow page
  238.  *            OVFLPAGE -- 0
  239.  *
  240.  * FULL_KEY_DATA 
  241.  *        This must be the first key/data pair on the page.
  242.  *        There are two cases:
  243.  *
  244.  *        Case 1:
  245.  *            This page contains a key and the beginning of the
  246.  *            data field, but the data field is continued on the
  247.  *            next page.
  248.  *
  249.  *            Page format is:
  250.  *            KEY_OFF FULL_KEY_DATA OVFL_PAGENO DATA_OFF
  251.  *
  252.  *            KEY_OFF -- offset of the beginning of the key
  253.  *            FULL_KEY_DATA -- 3
  254.  *            OVFL_PAGENO - page number of the next overflow page
  255.  *            DATA_OFF -- offset of the beginning of the data
  256.  *
  257.  *        Case 2:
  258.  *            This page contains the last page of a big data pair.
  259.  *            There is no key, only the  tail end of the data
  260.  *            on this page.
  261.  *
  262.  *            Page format is:
  263.  *            DATA_OFF FULL_KEY_DATA <OVFL_PAGENO> <OVFLPAGE>
  264.  *
  265.  *            DATA_OFF -- offset of the beginning of the data on
  266.  *                this page
  267.  *            FULL_KEY_DATA -- 3
  268.  *            OVFL_PAGENO - page number of the next overflow page
  269.  *            OVFLPAGE -- 0
  270.  *
  271.  *            OVFL_PAGENO and OVFLPAGE are optional (they are
  272.  *            not present if there is no next page).
  273.  */
  274.  
  275. #define OVFLPAGE    0
  276. #define PARTIAL_KEY    1
  277. #define FULL_KEY    2
  278. #define FULL_KEY_DATA    3
  279. #define    REAL_KEY    4
  280.  
  281. /* Short hands for accessing structure */
  282. #define BSIZE        hdr.bsize
  283. #define BSHIFT        hdr.bshift
  284. #define DSIZE        hdr.dsize
  285. #define SGSIZE        hdr.ssize
  286. #define SSHIFT        hdr.sshift
  287. #define LORDER        hdr.lorder
  288. #define OVFL_POINT    hdr.ovfl_point
  289. #define    LAST_FREED    hdr.last_freed
  290. #define MAX_BUCKET    hdr.max_bucket
  291. #define FFACTOR        hdr.ffactor
  292. #define HIGH_MASK    hdr.high_mask
  293. #define LOW_MASK    hdr.low_mask
  294. #define NKEYS        hdr.nkeys
  295. #define HDRPAGES    hdr.hdrpages
  296. #define SPARES        hdr.spares
  297. #define BITMAPS        hdr.bitmaps
  298. #define VERSION        hdr.version
  299. #define MAGIC        hdr.magic
  300. #define NEXT_FREE    hdr.next_free
  301. #define H_CHARKEY    hdr.h_charkey
  302.